class Solution {
public:
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    vector<int> countBits(int num) {
        // write your code here
        vector<int> vec;
        for (int i = 0; i <= num; i++) {
            vec.push_back(bits(i));
        }
        return vec;
    }

    int bits(int num) {
        num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
        num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
        num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
        num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);

        return (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
    }
};

class Solution {
public:
    /**
     * @param num: a non negative integer number
     * @return: an array represent the number of 1's in their binary
     */
    vector<int> countBits(int num) {
        // write your code here
        vector<int> vec(num+1, 0);
        int msb = 1;
        for (int i = 1; i <= num; i++) {
            if (i > 1 && (i & (i - 1)) == 0) {
                msb <<= 1;
            }
            vec[i] = vec[i & ~msb] + 1;
        }
        return vec;
    }
};
